package primary.primary0;

import java.util.HashMap;
import java.util.Map;

public class S0560和为k的子数组 {
    class Solution {
        /**
         * 不会写，这个暴力肯定超时
         * 83，居然没超时
         * 背包问题，背包的排列方式数量 ，无序
         * 2^20000必然不能枚举了，咋剪枝都不管用，
         * 即使是二维，也有4*10^8个，也不可能，必然是递推
         * 等一下，连续的，那。。。
         */
        public int subarraySum(int[] nums, int k) {
            if(nums == null || nums.length == 0){
                return -1;
            }
            // 遍历所有子数组
            int totalLen = nums.length;
            int count = 0;
            for(int i = 0; i < totalLen; i ++){
                int sum = 0;
                for(int j = i; j < totalLen; j++){
                    sum += nums[j];
                    // 因为nums[i]和k都是可正可负的，所以要一直加
                    if(sum == k){
                        count++;
                    }
                }
            }

            return count;
        }
    }

    class Solution2 {
        /**
         * 95
         * 前缀和，看答案的
         * 递推，寻找位置n结尾，和为k的子数组数量，
         * 如果m -> n 加起来是k，就表示 sumn - summ = k
         * 此时如果知道sumn的值，那就表示 只要符合 summ = sumn - k 的m，都能满足m->n加起来是k
         */
        public int subarraySum(int[] nums, int k) {
            if(nums == null || nums.length == 0){
                return -1;
            }

            int sum = 0;
            int result = 0;
            // mark:Integer作为hashMap的key，会不会有key冲突的问题?得看下
            // https://blog.csdn.net/qq_40703471/article/details/126655439
            Map<Integer, Integer> record = new HashMap<>();
            // mark:注意第一个值也就是m可以啥都没有的
            record.put(0,1);
            for(int n = 0; n < nums.length; n ++){
                sum += nums[n];
                Integer matchedCount = record.get(sum - k);
                // 以n结尾有多少个
                if(matchedCount != null){
                    result += matchedCount;
                }
                // 本次记录添加
                Integer curSumRecord = record.get(sum);
                if(curSumRecord == null){
                    record.put(sum, 1);
                }else{
                    record.put(sum, curSumRecord + 1);
                }
            }
            return result;
        }
    }
}
